Scheduling for Stable and Reliable Communication over Multiaccess Channels and Degraded Broadcast Channels

摘要

Information-theoretic arguments focus on modeling the reliability ofinformation transmission, assuming availability of infinite data at sources,thus ignoring randomness in message generation times at the respective sources.However, in information transport networks, not only is reliable transmissionimportant, but also stability, i.e., finiteness of mean delay incurred bymessages from the time of generation to the time of successful reception.Usually, delay analysis is done separately using queueing-theoretic arguments,whereas reliable information transmission is studied using information theory.In this thesis, we investigate these two important aspects of datacommunication jointly by suitably combining models from these two fields. Inparticular, we model scheduled communication of messages, that arrive in arandom process, (i) over multiaccess channels, with either independent decodingor joint decoding, and (ii) over degraded broadcast channels. The schedulingpolicies proposed permit up to a certain maximum number of messages forsimultaneous transmission. In the first part of the thesis, we develop a multi-class discrete-timeprocessor-sharing queueing model, and then investigate the stability of thisqueue. In particular, we model the queue by a discrete-time Markov chaindefined on a countable state space, and then establish (i) a sufficientcondition for $c$-regularity of the chain, and hence positive recurrence andfiniteness of stationary mean of the function $c$ of the state, and (ii) asufficient condition for transience of the chain. These stability results formthe basis for the conclusions drawn in the thesis.